import java.util.LinkedList;
import java.util.List;

/**
 * 自定义拉链式哈希表
 * @param <K>
 * @param <V>
 */
public class MyChainingHashMap<K, V> {

    private static class KVNode<K, V> {
        K key;
        V value;

        KVNode(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    // 哈希表的底层数组，每一个数组元素都是一个链表，链表中每个节点是KVNode键值对
    private LinkedList<KVNode<K, V>>[] table;
    // 哈希表中存入的键值对个数
    private int size;
    // 底层数组的初始容量
    private static final int INITIAL_CAPACITY = 4;

    public MyChainingHashMap() {
        this(INITIAL_CAPACITY);
    }

    public MyChainingHashMap(int initialCapacity) {
        size = 0;
        // 保证底层数组的容量至少为1，因为hash函数中有求余运算，避免出现除以0的情况
        initialCapacity = Math.max(initialCapacity, 1);
        // 初始化哈希表
        table = (LinkedList<KVNode<K,V>>[]) new LinkedList[initialCapacity];
        for (int i = 0; i < table.length; i++) {
            table[i] = new LinkedList<>();
        }
    }

    // 增改
    // 添加key -> value键值对
    // 如果键key存在，则将值修改为value
    public void put(K key, V value) {
        if (key == null) {
            throw new IllegalArgumentException("key can not be null");
        }
        LinkedList<KVNode<K, V>> list = table[hashCode(key)];
        // 如果key之前存在，则修改对应的value
        for (KVNode<K, V> node : list) {
            if (node.key.equals(key)) {
                node.value = value;
                return;
            }
        }

        // 如果key不存在，则添加新的键值对
        list.add(new KVNode<K, V>(key, value));
        size++;
        // 如果元素数量超过了负载因子，则进行扩容
        if (size >= table.length * 0.75) {
            resize(table.length * 2);
        }

    }

    // 删除key以及对应的value
    public void removeKey(K key) {
        if (key == null) {
            throw new IllegalArgumentException("key值为空");
        }
        LinkedList<KVNode<K, V>> list = table[hashCode(key)];
        // 如果key存在，则删除key，减少size
        for (KVNode<K, V> node : list) {
            if (node.key.equals(key)) {
                list.remove(node);
                size--;
                ;
                // 缩容，当负载因子小于0.125时，进行缩容
                if (size <= table.length / 8) {
                    resize(table.length / 4);
                }

                return;
            }
        }
    }

    // 返回key对应的value，如果key不存在，则返回null
    public V get(K key) {
        if (key == null) {
            throw new IllegalArgumentException("key值为空");
        }
        LinkedList<KVNode<K, V>>  list = table[hashCode(key)];
        for (KVNode<K, V> node : list) {
            if (node.key.equals(key)) {
                return node.value;
            }
        }

        return null;
    }

    // 返回所有键
    public List<K> getKes() {
        LinkedList<K> keys =new LinkedList<>();
        for (LinkedList<KVNode<K, V>> list : table) {
            for (KVNode<K, V> node : list) {
                keys.add(node.key);
            }
        }

        return keys;
    }

    // 其他工具方法
    public int size() {
        return size;
    }

    private int hashCode(K key) {
        return (key.hashCode() & 0x7fffffff) % table.length;
    }

    private void resize(int newCap) {
        // 构造一个新的HashMap
        // 避免newCap为0，造成求模运算时出现除0
        newCap = Math.max(newCap, 1);
        MyChainingHashMap<K, V> newMap = new MyChainingHashMap<>(newCap);
        // 穷举当前所有键值对
        for (int i = 0; i < table.length; i++) {
            for (KVNode<K, V> node : table[i]) {
                // 将键值对转移到新的HashMap中
                newMap.put(node.key, node.value);
            }
        }

        // 将当前HashMap的底层table换掉
        this.table = newMap.table;
    }
}
